题解：P14566 【MX-S12-T1】取模

归档17

题解17

265 字

1 分钟

题解：P14566 【MX-S12-T1】取模

2025-11-22

题面传送门：P14566 【MX-S12-T1】取模

题目大意#

选取一个正整数 $p$ 使 $a$ 数组中各项对这个正整数取模的结果的极差（即最大值与最小值的差）最大

思路讲解#

由上文可知，本题是一个找最值的题目，因此考虑贪心

贪心具体分两种思路：

取模结果极差最大，则先找到 $a$ 数组中的最大值 $maxx$ ，正整数 $p$ 则为 $maxx+1$ 。此时的结果为 $a$ 数组的最大值-最小值
我们发现思路1无法通过样例3和4，此时考虑将 $p$ 直接定为 $maxx$ ，此时 $a$ 数组中取模结果最小值为 $0$ ，最大值为 $a$ 数组中的次大值

我们将这两种思路所得结果进行比较即可。

AC代码#

1
#include<bits/stdc++.h>
2
using namespace std;
3
int t,n,a[100005],b1[100005],b2[100005],maxx;
4
int main(){
5
  cin>>t;
6
  for(int z=1;z<=t;z++){
7
    cin>>n;
8
    maxx=-1;
9
    for(int i=1;i<=n;i++){
10
      cin>>a[i];
11
      maxx=max(maxx,a[i]);
12
    }
13
    for(int i=1;i<=n;i++){
14
      b1[i]=a[i]%(maxx+1);
15
      if(maxx!=0) b2[i]=a[i]%maxx;//防止对0取余时报错
16
    }
17
    sort(b1+1,b1+n+1);//可改为打擂台找最值
18
    sort(b2+1,b2+n+1);;//可改为打擂台找最值
19
    cout<<max(b1[n]-b1[1],b2[n]-b2[1])<<endl;
20
  }
21
  return 0;
22
}